In order for two unspecified parties to transmit data without having the data tampered with by a malicious third party in an ad-hoc short-haul radio communication such as ad-hoc radio communication that does not utilize a specific infrastructure, it is necessary to share a cipher key that is unknown to the malicious third party. However, a method for properly setting a value behind the cipher key during communication is complicated, therefore, particularly under the circumstance where communicating parties meet for the first time, it is impractical that they exchange the cipher key by parol or memo writing. One method for automatically sharing a cipher key is to share a public key first and then encrypt the cipher key using that public key to share. However, there is a risk of Man-in-the-middle attack (For details on Man-in-the-middle attack, refer to the publication titled “APPLIED CRYPTOGRAPHY”, John Wiley & Sons, Inc., pages 48–50, by Bruce Schneier).
Now the risk of data tampering in the Man-in-the-middle attack will be summarized. FIG. 1 shows that a malicious third party C intervenes between a source A and a destination B in an ad-hoc radio communication system 10, without both parties noticing this intervention. Despite parties A and B believe that a communication path is established between them directly as shown in FIG. 1(a), practically the third party may intervene between them as shown in FIG. 1(b). Now it will be described how the Man-in-the-middle attack is performed by way of a concrete example.
A common procedure for establishing a radio cipher communication path is as follows.                Procedure 1: The source makes a call to an unspecified number of parties using an ID of the destination it desires to communicate with.        Procedure 2: If the destination is located within the coverage area, it receives the ID (i.e., own ID).        Procedure 3: The destination communicates its operating conditions or the like to the source.        Procedure 4: Both parties determine the operating parameters together necessary for establishing a communication path (e.g., selection and setting of a communication path to be used, exchange of a cipher etc.).        Procedure 5: The communication path is established and mutual communication starts.        
The timing when the malicious third party is most liable to intervene at the position C shown in FIG. 1 is the timing when both parties subject to wiretapping begin the radio communication face to face. That is, the intervention may occur during above listed procedures 1–3. FIG. 2 and FIG. 3 shows an example of methodology for a malicious third party to intervene at the position C shown in FIG. 1. According to the nature of the radio wave, the source A is forced to make a call to all surrounding destination candidates using a specific ID (procedure 1). The destination B listens for a call of its own ID (procedure 2), and responds to source A (procedure 3). At this moment, a malicious third party tries to make a pretense as mentioned below, by responding to a call to an ID other than its own or making a call using an ID other than its own. First of all, the malicious third party sends out a noise of the same frequency band against a response from destination B and hinders source A from listening for that response. At this moment, destination B does not know the fact of noise, so that it goes on to the procedure 4 and waits for the start of sessions from source A in the procedure 4. Since source A is not in the procedure 4, destination B returns to a condition again where it listens for a call of its own ID after the time-out. On the other hand, source A does not get a response from destination B, thus it usually makes a call using the same ID after the time-out (procedure 1). That is, source A and destination B try to synchronize the procedure each other, then they become aware of the failure by the time-out, then they return to the original conditions.
The malicious third party waits in tune with the timing when source A makes a call again using the same ID, and further waits in tune with the timing when destination B again starts listening for the call of its own ID. Thereafter, the malicious third party C responds to the call from source A by pretending destination B, and makes a call to destination B that starts listening for a call of its own ID by pretending source A. Of course, the malicious third party has a capability to change its own ID to any ID. The reason why the malicious third party can make such two pretense behavior is that the timing is not the same when source A and destination B return to the original conditions due to out of synchronization of the mutual procedure. This results from the fact that the timing when source A and destination B start waiting for a next event is originally different and that an event subject to the time-out is also different, hence the time-out period itself is different.
Due to this pretense maneuver, source A believes that it received a normal response from a proper destination B and proceeds with the malicious third party C on and after the procedure for establishing the communication path, i.e., procedure 4, while destination B believes that it received a call from a proper source A and-proceeds with the malicious third party C as well. When proceeding to the procedure 5, the malicious third party can wiretap by relaying communication data between both parties, without coming to a knowledge of both parties A and B who want to secure the communication path by themselves. Utilizing this pretense (i.e., relay), a public key that source A is to send to destination B can be tampered with by the third party C and changed with a public key corresponding to a private key that the third party C prepared in advance. As a result, a cipher communication path that is essentially constructed between source A and destination B is only effective between source A and the third party C, while another communication path is established between the third party C and destination B by the third party C. That is, encrypted data sent from source A is decoded by the third party C, then it is transmitted over a cipher communication path between the third party C and destination B, with applying another encryption. The same applies to the reverse transmission. Despite both source A and destination B establish the cipher communication path in a normal procedure, they are changed their public key without knowing it, consequently wiretapped. Such an attack (i.e., wiretapping by pretense) is called Man-in-the-middle attack. Since the cipher communication path itself is safe, it is essential that both parties who communicate truly share the same public key, as a countermeasure against such an attack.
[Problems to be Solved by the Invention]
As a countermeasure against the-Man-in-the-middle attack, it is conceivable to display a personal ID (typically the name of an opponent) described in a certificate on the sending side and destination side to compare, using the certificate issued by a certification body. However, it costs to issue the certificate. Also, when utilizing a certification body, it is necessary to register one's identity for authentication, thus resulting in publishing own identity to an opponent, whereby anonymity can not be kept. Further, when utilizing a service such as Yellow Page that specifies a user from a public key, there is needed a secure network connection based on the phone line, for example, which costs for transaction.